/*
 * 8.3
 * Write a method that returns all subsets of a set.
 */
#include <stdio.h>

/* XXX: time complexity is O(2^n). */

// XXX: do not print directly,
// print is done only once in every level, but it has many more sub decision tree.
void subset(int *arr, int i, int n, char *bits)
{
    if (i == n) { // XXX: was i+1...
        printf("{ ");
        for (int j = 0; j < n; j++) {
            if (bits[j]) {
                printf("%d ", arr[j]);
            }
        }
        printf("}\n");
        return;
    }
    bits[i] = 0;
    subset(arr, i+1, n, bits);
    bits[i] = 1;
    subset(arr, i+1, n, bits);
}

int main()
{
    int arr[] = { 1, 2, 3 };
    const int n = sizeof(arr)/sizeof(arr[0]);
    char bits[n];
    subset(arr, 0, n, bits);
    return 0;
}
